package LimitedTimeGame.Day_0221;

/**
 * @author zxc
 * @date 2023/02/21 09:19
 **/

import java.util.Arrays;

/**
 * 题目 ：灌溉花园的最少水龙头数目
 * 题目详述 ：
 * 在 x 轴上有一个一维的花园。花园长度为n，从点0开始，到点n结束。
 * 花园里总共有n + 1 个水龙头，分别位于[0, 1, ..., n] 。
 * 给你一个整数n和一个长度为n + 1 的整数数组ranges，其中ranges[i] （下标从 0 开始）表示：
 * 如果打开点i处的水龙头，可以灌溉的区域为[i - ranges[i], i + ranges[i]]。
 * 请你返回可以灌溉整个花园的最少水龙头数目。如果花园始终存在无法灌溉到的地方，请你返回-1。
 *
 * 提示：
 * 1 <= n <= 104
 * ranges.length == n + 1
 * 0 <= ranges[i] <= 100
 *
 */
public class MinTaps {
    public static void main(String[] args) {
        System.out.println(minTaps(7, new int[]{1,1,1,1,1,1,0,0}));
    }
    /**
     * 思路 ：
     * 即，使用辅助数组dp，来存储每个水龙头所能够灌溉到的区间
     * && 同时，对于dp进行排序，按照dp[0]从小到大进行排序，按照dp[1]从大到小进行排序;
     *
     * @param n
     * @param ranges
     * @return
     */
    public static int minTaps(int n, int[] ranges) {
        // 即，使用辅助数组dp，来存储所有区间
        int[][] dp = new int[n + 1][2];
        int len = ranges.length;
        // 计算各个区间的取值范围，同时将其加入到dp数组中;
        for(int i = 0 ; i < len ; i++){
            dp[i][0] = i - ranges[i];
            dp[i][1] = i + ranges[i];
        }
        // 对于dp数组进行排序;
        Arrays.sort(dp , (p1 , p2) -> {
            // 按照p[0]进行从小到大的排序;
            if(p1[0] != p2[0]){
                return p1[0] - p2[0];
            }
            // 按照p[1]进行从大到小的排序;
            else {
                return p2[1] - p1[1];
            }
        });
//        for(int i = 0 ; i < len ; i++){
//            System.out.println(dp[i][0] + " " + dp[i][1]);
//        }


        int count = 1;
        // 通过变量previous，来框定所要遍历区间的上区间取值
        int previous = dp[0][0];
        // 特殊情况 ：即，当dp数组中最小数组对 不能够取到0的话，则代表不能够灌溉所有;
        if(previous > 0){
            return -1;
        }
        // 记录前一个水龙头，正向x轴方向所能够到达的最远距离
        int last = dp[0][1];
        // 变量k，永远指向 下一个需要遍历的元素;
        int k = 1;
        // 即，寻找到 符合条件： 区间前面的取值 <= 0 && 区间后面取值最大 的区间
        // 即，在dp数组中，选择dp[x][y] （x <= 0; y是最大值）;
        // 同时，变量k 指向第一个dp[i][0]大于0的dp数组下标
        for(int i = k ; i < len && dp[i][0] <= 0 ; i++){
            if(dp[i][1] > last){
                last = dp[i][1];
            }
            k = i + 1;
        }
        // 开始
        previous = 1;
        // while循环结束条件 ：即，last当前最大区间 < n;
        // 即，需要遍历 满足previous <= dp[i][0] <= last条件的所有元素
        // 注意 ：从数组dp中第k个元素开始遍历，即第k个元素是第一个 >= previous的元素
        while(last < n){
            int temp = last;
            for(int i = k ; i < len && dp[i][0] >= previous && dp[i][0] <= temp ; i++){
                last = Math.max(last , dp[i][1]);
                k = i + 1;
            }
            // 若是两个区间之间的交集为 null的话，则代表不能灌溉到所有地方;
            if(last == temp){
                return -1;
            }
            previous = temp + 1;
            count++;
        }
        return count;
    }
}
